The field of this invention is coding of numeric data. More precisely, the invention relates to error correction codes. The invention is particularly but not exclusively applicable to the coding of source data organized into data blocks independent from each other and therefore that need to be coded and decoded individually, and coding of data flows (convolutional coding).
Many coding techniques for correcting transmission errors are already known. In particular, refer to documents by F. J. McWilliams and N. J. A. Sloane [1], S. B. Wicker [2], and V. Pless et al [3] (all references mentioned in this application have been grouped in the appendix to simply reading). Error correction codes are used to correct transmission errors inherent to all communication channels. Thus, they are very frequently used in telecommunications, remote broadcasting and information storage, for example on laser disks and magnetic disks, etc.
For example, these errors may be caused by thermal noise in electronic components of the receiver, accidental or deliberate electromagnetic interference, echoes or multiple propagation in the case of radio propagation (for example for radiotelephony systems such as GSM, digital radio broadcasting such as DAB or digital television such as DVB) or in an electrical power network (for example for telecommunications on the electrical network).
The first studies on error correction codes date from the 1940s. In his articles written in 1948, Claude Shannon [4] wrote the foundations of the information theory based on which digital communication systems are still (and always will be?) designed.
One of Shannon""s results is his theorem concerning the limiting capacity of a communication channel, which is defined by the following well known formula:   C  =      B    ·          Log      ⁡              (                  1          +                      S            N                          )            
where the capacity C of the channel is an information throughput expressed in bits/s, B is the pass band of the channel in Hz and S/N is the ratio of the signal and noise powers in the pass band.
This theorem is expressed as follows: xe2x80x9cThere is a transmission capacity C (in bits per second) associated with every channel. There are error correction codes such that the information can be transmitted through a channel at a rate lower than its capacity C with an arbitrarily low bit error rate by using a sufficiently long error correction codexe2x80x9d.
Unfortunately, Shannon""s theorem is no more than a proof of existence. His publication was the starting point for a search for xe2x80x9cgoodxe2x80x9d codes that has now been going on for 50 years. The main codes that have attracted the attention of the telecommunications community were firstly block codes to transmit bit packets; Hamming codes, Golay codes, Reed-Muller codes, BCH codes, Reed-Solomon codes, etc.
The principle of block error correction codes was invented by R. W. Hamming in 1950: starting from k useful information bits, (nxe2x88x92k) redundancy bits are calculated using modulo 2 additions of k information bits, therefore the total length of each block, also called a code word, is n bits. On reception, if there are any errors present in the received n-bit word, the presence of the (nxe2x88x92k) redundancy bits adjacent to the k useful information bits can be used to correct some of the errors present.
If the ratio of the signal/noise powers exceeds a particular value, then the cost of the information flow occupied by code redundancy bits is more than compensated by the reduction, or possibly almost complete elimination, of the bit error rate (BER) after decoding. This gain in performance is called the coding gain, for a fixed BER, and is given in decibels (dB). A coding gain of 3 dB means that the power of the signal transmitted with coding can be halved compared with the same BER without coding (3 dB≈10.Log10(2)).
Another large and more recent coding family is the convolutional codes family introduced by P. Elias [5] in 1955. These codes transform an infinite series of information symbols into several other infinite series of information symbols. These codes were invented to transmit continuous information flows. A. J. Viterbi [6] (in 1967) and G. D. Forney [7] (in 1973) have demonstrated the possibilities of efficiently decoding xe2x80x9csmallxe2x80x9d convolutional codes with the xe2x80x9cViterbixe2x80x9d algorithm (an algorithm based on the dynamic programming theory (See Bellmann [8] (1957)).
Block (error correction) codes and convolutional codes may be methoded using the same theoretical tools and the same decoding methods. Block codes and convolutional codes can be represented by special graphs called xe2x80x9ctrellisxe2x80x9d from which their weight distribution can be calculated and that can be used for decoding using the Viterbi algorithm (see Forney [7] and McEliece [9]).
Each code word is represented by a different path in the trellis and the best path, in other words the code word closest to the received word, is found by decoding using the Viterbi algorithm. But for a block code or for a convolutional code, the complexity of the decoding increases exponentially at the power of 2(nxe2x88x92k) for a block code, and 2v for a convolutional code (were n is the size of the memory of the convolutional coder). The dilemma is that as the length and power of the code increases, it corrects more errors, but it is also more expensive in time and decoding equipment.
Recently, in 1993, C. Berrou and A. Glavieux [10] presented a new coding scheme usually called the xe2x80x9cturbo-codexe2x80x9d. There are four main concepts in turbo-codes:
1) Use recursive convolutional coding, in other words with an infinite pulse response (and not a finite pulse response as is conventionally used).
2) Code useful information bits once in their initial order, then code the same useful data a second time but in a different order, in other words swapped around. The useful bits are transmitted only once, and coders only transmit their redundancies. Swapping, also called interlacing, is xe2x80x9cmagicxe2x80x9d since the code is able to correct more errors as it becomes larger. Interlacing decorrelates errors created by the transmission channel.
3) Use soft decoding techniques introduced by Bahl et al (BCJR algorithm) [11], G. Battail [12], or Hagenauer (SOVA (xe2x80x9cSoft-Output Viterbi Algorithmxe2x80x9d) [13], etc.
4) By definition, let the output Li (of each elementary soft decoder i receiving xe2x80x9cinformationxe2x80x9d Li(0) in iteration i) be the sum of the received initial xe2x80x9cinformation L0 and extracted or extrinsic information Wi such that LI=L0+Wi. In the next iteration (i+1), only part of the extrinsic information is reinjected such that Li+1(0)=L0+ai+1Wi, where the coefficients ai vary from 0 in the first iteration and can reach 1.0 in the last iteration. There coefficients ai are optimized to minimize the BER starting from a given signal/noise ratio. Strictly speaking, the L and W quantities are logarithms of the probability ratio and not information quantities.
Berrou and Glavieux""s first turbo-codes were convolutional codes based on a large swap matrix (256xc3x97256=65536) with performances close to the Shannon limit for low signal to noise ratios. But some of the most recent telecommunication and radio broadcasting systems require small information packets to be transmitted (for example radio back scattering, mobile telephone, cordless ATM, Internet, etc.).
Furthermore, the disadvantage of large swaps is an incompressible delay in methoding which can be very annoying in a real time service, for example as in a telephone conversation. This is why research is continuing to find good block xe2x80x9cturbo-codesxe2x80x9d. In particular, R. Pyndiah et al [14] have adapted the iterative decoding concept to Elias product codes [5] for small block codes (n less than 1024). And recently in 1997, Berrou et al [17] adapted their turbo-codes (by closing trellis) to the construction of high performance block codes of this order of size (n less than 2048) called FOTC (Frame Oriented Turbo Codes).
Block codes presented by Berrou and Pyndiah are some of the best known codes for their size and efficiency categories (0.5 less than r less than 1), for a decoding complexity that enables manufacturing of hardware with an excellent quality/price ratio.
For a given block length n and for a given correction capacity
t=[(dxe2x88x921)/2]
(where d is the minimum Hamming distance between two code words), there are more or less severe upper limits to the performances that can be expected. The best of the known upper limits is the McEliece et al limit [1,2], represented (11) as a solid line in FIG. 1. The Gilbert-Varshamov limit 12 is also shown in a dashed line.
For a fixed relative d/n distance, it is impossible to find a code with an efficiency k/n greater than the McEliece limit. Furthermore, it is said that the code family is good if:             lim              n        →        ∞              ⁢          (              d        /        n            )        ≠  0
For example, for an efficiency of k/n=0.5, the McEliece limit on the minimum relative distance is d/n £ 0.18. Therefore, if n=1024 bits, the maximum number of errors that could be corrected is 91.
At the present time, turbo-codes are the most efficient correction codes for a BER of the order of 10-4. The improvement compared with other techniques is not as significant when this BER is very low, for example of the order of 10-10.
Furthermore, the efficiencies obtained (conventionally xc2xd) are not optimum.
One particular objective of the invention is to overcome these various disadvantages in the state of the art.
More precisely, one purpose of the invention is to provide an error correction coding method with better performances than known codes. In particular, one objective of the invention is to supply such a method very close to the McEliece limit.
Another purpose of the invention is to supply this type of coding method that can give a very large gain particularly when error rates are very low, of the order of 10-10.
Another purpose of this invention is to supply this type of method to give better efficiency than is possible with known coding techniques for a given error rate (for example to change from an efficiency xc2xd to xc2xc or xe2x85x9).
Another purpose of the invention is to supply this type of coding method that is adapted to coding of data blocks with an average length n, for example between 128 and 2048 bits.
Yet another purpose of the invention is to supply a coding method of this type that can easily be implemented in VLSI.
Another purpose of the invention is to supply a corresponding decoding method with reasonable complexity, and particularly that has a ratio or performance/complexity that is competitive compared with the best known codes.
These purposes, and others that will become clear later, are achieved according to the invention using an error correction coding method of the type associating a block of coded data with a series of source data, to be transmitted to at least one receiver, comprising:
at least two coding steps each comprising at least two basic coding modules, each of said coding steps receiving a series of data to be methoded, distributed between said basic coding modules, and outputting a series of methoded data from said basic coding modules;
and at least one mixing step, said mixing step being inserted between two successive coding steps, a first coding step and a second coding step, distributing the methoded data output from each basic coding module in said first coding step between at least two basic coding modules in said second step.
This type of coding method can give a large minimum distance for a given efficiency. Thus the minimum distance of this type of code (192, 96) with efficiency xc2xd, built based on the example described below, is close to 30. Furthermore, the weight distribution is close to optimum.
Advantageously, each step corresponds to a stage in the structure of a corresponding coding device. This structure facilitates understanding of the invention. However, the device can use the method according to the invention in any other suitable form, and particularly in an essentially software form in which one (or several) methodors perform the corresponding methoding.
In this case, mixing means any type of distribution, swapping, rotation, and more generally functions of several inputs to the mixing step (additions, multiplications, weightings, etc.).
As will be seen later, this method may easily be implemented in the form of a pipe-line machine, particularly in a VLSI.
Advantageously, a systematic or pseudo-systematic code is used.
Thus, said block of coded data to be transmitted advantageously comprises at least some of said source data and at least some methoded data output from the last coding stage, and preferably all said source data.
According to one advantageous embodiment of the invention, said coded data block comprises methoded data output from at least two coding steps. For example, data calculated in the last step, and in at least one previous step, can be used. An appropriate compromise will be chosen between the decoding quality (taking account of the largest possible amount of information) and the efficiency, depending on the needs.
In one particular embodiment, at least one of said mixing steps uses at least one swap matrix. It would also be possible to make at least one of said mixing steps distribute the methoded data to at least two distinct coding steps. Obviously, the two aspects may be combined in the same device.
Similarly, at least one item of said source data and/or at least one item of said methoded data may be duplicated at least once, in order to form at least two items of data to be methoded.
Another possibility would be that at least one of said source data would be directly input into a coding step other than the first coding step.
Obviously, these various aspects may be combined and chosen preferably to give the best coding, while decoding remains sufficiently simple and efficient.
According to a particular embodiment of the invention, the coding method comprises at least two of said coding units each comprising at least two coding steps and at least one mixing step inserted between two successive coding steps, said source data each being input into each of said coding units in different input orders.
In particular, it may comprise at least one mixing unit, modifying the order in which said source data are input into one of said coding units.
This thus gives two (or more) separate sets of redundancy data.
According to one advantageous embodiment, the coding method applies puncturing on at least some of said data to be methoded and/or on at least some of said methoded data.
Advantageously, said coding modules use a redundancy code with length nxe2x88x92k less than or equal to 12.
As already mentioned, the invention is particularly applicable to coding of data blocks with a relatively limited size.
According to a first embodiment that is particularly easy to implement, all said coding modules are identical. For example, said coding modules may use a Reed-Mxc3xcller code.
Advantageously, in this case at least one of said mixing steps uses a xe2x80x9cparityxe2x80x9d swap that groups inputs with even indexes, and inputs with odd indexes, at the output.
According to one preferred embodiment, the swap thus performs the following operations for a swap length k:
inputs with even indexes i=2p are sent to outputs j=p, p=0, 1, . . . int[k/2]xe2x88x921;
inputs with odd indexes i=2p+1 are sent to outputs j=p int[k/2],
where int[x] is the function giving the integer part of x.
According to one advantageous aspect of the invention, the coding method uses mixing steps involving a parity swap, and comprises:
three coding steps each comprising three basic coding modules;
three coding steps each comprising four basic coding modules;
five coding steps each comprising nine basic coding modules,
said basic coding modules using an extended Hamming code [8,4].
According to one advantageous embodiment, said basic coding modules are built using elementary coding blocks associating the (x0, x0+x1) pair with the (x0, x1) pair.
Therefore in this approach, there are two construction (or nesting) levels for the final code.
Another code that is advantageous in that it is extremely simple is a (4,2) code, for example that associates the values (x0, x1, x0, x0+x1) with the (x0, x1) pair. The trivial code that systematically associates x0 with x0 can also be used, in combination with other basic codes like that mentioned above.
This type of code can give very simple embodiments, for example based on tables of values, due to the small number of possible states. For example, they can be used to build the Hamming H code [8, 4, 4].
According to another embodiment, at least two of said coding modules are different.
Another advantageous possibility is that at least one of said basic coding modules is used in a trellis defining a set of paths bijectively associated with a set of code words, and outputting optimum path metrics according to a predetermined criterion.
Codes built on this principle are called xe2x80x9cCortex II codesxe2x80x9d, and codes obtained using the previous technique are called xe2x80x9cCortex I codesxe2x80x9d.
Advantageously, at least one of said mixing steps generates at least one output that is a function of at least two inputs to said mixing step.
In other words, at least one (and conventionally all) coder outputs are distributed to several coder inputs in the next stage.
In particular, said function can use at least one summation, a multiplication and/or a weighting.
According to one advantageous aspect of the invention, said inputs to said function are path metrics.
Furthermore, the structure can advantageously be looped back. Therefore, said coding and mixing steps are iterated at least twice, the first and last mixing steps forming a single step.
Advantageously, said method comprises a step in which at least one of the following elements is checked and/or adjusted:
coding type and/or characteristic used by at least one of the basic coding modules;
mixing used by at least one of said mixing steps;
puncturing used on at least some of said data to be methoded and/or on at least some of said methoded data;
number of coding steps.
Said check and/or said adjustment can systematically act on a given period and/or as a function of at least one item of information representative of at least one of the aspects belonging to the group including:
at least one characteristic of the transmission channel;
at least one characteristic of the receiver;
at least one characteristic of the source signal.
The invention also relates to error correction coding devices using the method described above. In this type of device, a coded data block is associated with a series of source data, and the coded data block will be transmitted to at least one receiver using:
at least two coding stages each using at least two basic codings, each of said coding stages receiving a series of data to be methoded, distributed between said basic coding and outputting a series of methoded data corresponding to said basic coding;
and at least one mixing stage, said mixing stage being inserted between two successive coding stages, a first coding stage and a second coding stage, and distributing the methoded data corresponding to each basic coding of said first coding stage between at least two basic codings of said second stage.
As described above, each of said stages may actually correspond to a component (or set of components) or it may be used by one or several methodors controlled by a corresponding program.
The invention also relates to the corresponding decoding methodes and devices. Advantageously, this type of decoding method is iterative.
Preferably, said decoding method uses at least one of the techniques belonging to the group comprising:
decoding using a structure symmetric with the structure used during coding;
exhaustive decoding, according to which all possible code words are considered and the best is selected according to a predetermined selection criterion;
Viterbi type decoding, using a decoding trellis;
Chase decoding.
Advantageously, this type of decoding method uses at least two decoding steps, including at least two decoding modules, and at least one swap step inserted between two consecutive decoding steps, said steps being symmetric with the corresponding coding steps, each of said decoding modules comprising twice as many inputs and outputs as the corresponding coding module, to assure propagation of probability values from the input to the output side of the decoder, and secondly from the output to the input side of said decoder.
The result is a gradual convergence of decoded data in the two decoding directions.
As for coding, the step concept is similar to the stage concept for the corresponding device as described below.
Advantageously, the decoding method according to the invention uses at least one iteration of the following operations:
propagation of all said probability values towards the input side of said receiver, producing a first set of estimated values;
propagation of all said probability values towards the output side of said receiver, producing a second set of estimated values.
Preferably, said decoding determines path probabilities. Thus, in each iteration, each of said elementary decoding operations can determine a state probability for each possible corresponding coding state, and the state with the highest probability can be selected.
Advantageously, said state probability corresponds to the sum of a first probability value obtained starting from information bits and a second probability value obtained from redundancy bits.
Preferably, said probabilities are determined from probability laws.
In particular, said first (or second) probability associated with a given output from one of said elementary decodings may be obtained by determining the logarithm of the sum of the exponentials of the probabilities of states connected to said output, minus the logarithm of the sum of the exponentials of the probabilities received at the input, as information bits (or redundancy bits) for states connected to said output.
In other words, the extrinsic path probabilities are thus determined.
According to a particular embodiment of the invention, the decoding method comprises the following steps:
calculate state probabilities:
xe2x80x9cforwardsxe2x80x9d: Fi, based on information bits;
xe2x80x9cbackwardsxe2x80x9d: Bi, based on redundancy bits;
calculate global state probabilities:
Ei=Fi+Bi;
detect the maximum state probability Ei;
calculate the following probability values:
Vxe2x80x2(xj)=2 Log[xcexa3 exp(Ei/xjxe2x86x92Ei)]xe2x88x92Log[xcexa3 exp(Ei+Fi/xjxe2x86x92Ei)]
xe2x80x83(values propagated backwards, thus giving the information bits xj)
Vxe2x80x2(rj)=2 Log[xcexa3 exp(Ei/rjxe2x86x92Ei)]xe2x88x92Log[xcexa3 exp(Ei+Bi/rjxe2x86x92Ei)]
xe2x80x83(values propagated forwards, thus giving the redundancy bits rj)
where (Ei/xjxe2x86x92Ei) represents the probability of state Ei connected to output xj;
output said values to the next elementary decoding.
This step in calculating probability values could possibly be simplified by only including the state with the greatest probability in each of the exponential sums. This simplification does not significantly modify the decoding efficiency.
Preferably, when the decoding has reached a predetermined convergence criterion, possibly independent for each decoding module, an a posteriori probability is associated with each bit after equilibrium:
Vxe2x80x3(xj)=Log(xcexa3 exp(Ei/(xj=0)xe2x86x92Ei)xe2x88x92Log(xcexa3 exp(Ei/(xj=1)xe2x86x92Ei))
According to one advantageous characteristic of the invention, the decoding method may be used as a coding method with the redundancy inputs being forced to 0 and the information inputs corresponding to the data to be coded.
In this case, it may be used alternately firstly for coding and secondly for decoding data, for example for duplex type applications.
According to one preferred aspect of the invention, said basic decoding modules use trellis with nodes in which addition, comparison and/or selection operations are carried out and that output optimum path metrics. Additions, multiplications and/or weightings of at least two of said optimum path metrics are carried out in at least one of said mixing steps.
Regardless of whether coding and/or decoding according to the invention is concerned, at least one of said elementary codings and/or at least one of said elementary decodings and/or at least one of said swaps can advantageously be programmed.
For example, programmable decoding elements could be programmed using at least one of the following operating methods:
as a function of a predetermined command produced by coding;
as a function of a reference sequence coded by coding;
by blind learning starting from the received data.
It will be noted that the decoding efficiency can be sufficient to perform decoding without prior knowledge of the exact code used (blind learning).
According to one advantageous embodiment of the invention, said coding performs combined source coding and channel coding, and said decoding correspondingly performs combined channel decoding and source decoding.
Advantageously, said decoding also at least partially equalizes transmission channel effects.
According to the invention, it is possible that at least some of said calculations are made using preprogrammed tables (due to the simplicity of each coding and/or decoding module).
According to one advantageous embodiment of the invention, at least some of said calculations are done using analog components. The algorithm is inherently stable and is therefore well adapted to analog calculations. In particular, this may be the case for exponential and logarithm calculations, for which these types of components are very suitable. Obviously, these calculations could also be made digitally.
According to one advantageous variant of the invention, said basic coding and decoding modules use trellis, and the structures of said coding and mixing steps for coding, and said decoding and mixing steps for decoding, are identical.
In this case, the same structure can be used for coding and decoding (duplex).
The invention also relates to decoding devices using the decoding method described above, and any device for transmission and/or reception of at least one signal coded and/or decoded using the methodes described above.
One such transmission and/or reception device comprises signal transmission and/or reception means, at least some of these signals benefiting from coding according to the invention, and the corresponding coding and/or decoding methoding means.
The efficiency of the invention is such that transmission devices and reception devices can be made simpler and/or more efficient, capable of accepting channels with severe disturbance and/or rates higher than is possible with conventional techniques, and it can be used to make a complete transmission system.
Consequently, the invention is used for applications in a large number of fields, and particularly it can be used for techniques belonging to the group comprising:
transmission and/or broadcasting of digital signals (for example for applications grouped in the ITU xe2x80x9cIMT 2000xe2x80x9d project);
speech recognition and/or methoding.